package 力扣日常刷题.木22一月.第03天0110;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 帅小伙
 * @date 2022/1/10
 * @description
 */
public class Demo03回溯中等含k个元素的组合 {

    List<List<Integer>> res;
    public List<List<Integer>> combine(int n, int k) {
        res = new ArrayList<List<Integer>>();
        dfs(1,n,k,new ArrayList<>());
        return res;
    }

    void dfs(int index,int n,int k,ArrayList<Integer> list){
        // 加这个剪枝会快很多
        if(n-index +1 <k) return;
        if(k==0){
            res.add(new ArrayList<Integer>(list));
            return ;
        }
        if(index > n) return;

        dfs(index+1,n,k,list);
        list.add(index);
        dfs(index+1,n,k-1,list);
        list.remove(list.indexOf(index));
    }


}
